{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #招式拆解 I"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: dismantlingAction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #招式拆解 I"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>某套连招动作记作序列 <code>arr</code>，其中 <code>arr[i]</code> 为第 <code>i</code> 个招式的名字。请返回 <code>arr</code> 中最多可以出连续不重复的多少个招式。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>arr = \"dbascDdad\"\n",
    "<strong>输出: </strong>6\n",
    "<strong>解释:</strong> 因为连续且最长的招式序列是 \"dbascD\" 或 \"bascDd\"，所以其长度为 6。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>arr = \"KKK\"\n",
    "<strong>输出: </strong>1\n",
    "<strong>解释: </strong>因为无重复字符的最长子串是 <code>\"K\"</code>，所以其长度为 1。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>arr = \"pwwkew\"\n",
    "<strong>输出: </strong>3\n",
    "<strong>解释: </strong>因为连续且最长的招式序列是 \"wke\"，所以其长度为 3。&nbsp;    \n",
    "请注意区分 <strong>子串</strong> 与 <strong>子序列</strong> 的概念：你的答案必须是 <strong>连续招式</strong> 的长度，也就是 <strong>子串</strong>。而 \"pwke\" 是一个非连续的 <strong>子序列</strong>，不是 <strong>子串</strong>。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>提示：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= arr.length &lt;= 40000</code></li>\n",
    "\t<li><code>arr</code> 由英文字母、数字、符号和空格组成。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>注意：本题与主站 3 题相同：<a href=\"https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/\">https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/</a></p>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof](https://leetcode.cn/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof](https://leetcode.cn/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        hmap = {}\n",
    "        for c in arr:\n",
    "            hmap[c] = not c in hmap\n",
    "        for c in arr:\n",
    "            if hmap[c]: return c\n",
    "        return ' '\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, s: str) -> str:\n",
    "        dic = {}\n",
    "        for c in s:\n",
    "            dic[c] = not c in dic\n",
    "        for c in s:\n",
    "            if dic[c]: return c\n",
    "        return ' '\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        return next((i for i in arr if arr.count(i)==1),\" \")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        dic = dict() # python3中字典默认是有序的\n",
    "        for s in arr:\n",
    "            dic[s] = not s in dic\n",
    "        for k, v in dic.items():\n",
    "            if v is True: return k\n",
    "        return ' '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, list: str) -> str:\n",
    "        res = \" \"\n",
    "        # 暴力解法\n",
    "        word_dict = defaultdict(int)\n",
    "        for l in list:\n",
    "            word_dict[l] += 1\n",
    "        for l in list:\n",
    "            if word_dict[l] == 1:\n",
    "                return l\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        heatmap = {}\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] in heatmap:\n",
    "                heatmap[arr[i]] = False\n",
    "            else:\n",
    "                heatmap[arr[i]] = True\n",
    "        for key,value in enumerate(heatmap):\n",
    "            if heatmap[value] == True:\n",
    "                return value\n",
    "        return ' '\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        count = Counter(arr)\n",
    "        for k,v in count.items():\n",
    "            if v==1:\n",
    "                return k\n",
    "        return ' '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        new_dict = {}\n",
    "        if len(arr) == 0:\n",
    "            return \" \"\n",
    "        for element in arr:\n",
    "            if element not in new_dict:\n",
    "                new_dict[element] = 1\n",
    "            else:\n",
    "                new_dict[element] += 1\n",
    "        for key in new_dict.keys():\n",
    "            if new_dict[key] == 1:\n",
    "                return key\n",
    "        return \" \"       \n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        c = collections.Counter(arr)\n",
    "\n",
    "        for ch in arr:\n",
    "            if c[ch] == 1:\n",
    "                return ch \n",
    "        return \" \""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, list: str) -> str:\n",
    "        dic=collections.OrderedDict()\n",
    "        for c in list:\n",
    "            dic[c]=not c in dic\n",
    "        for k,v in dic.items():\n",
    "            if v:return k\n",
    "        return ' '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        record_1=[]\n",
    "        record_2=[]\n",
    "        for i in arr:\n",
    "            if i in record_2:\n",
    "                pass\n",
    "            elif i in record_1:\n",
    "                record_1.remove(i)\n",
    "                record_2.append(i)\n",
    "            else:\n",
    "                record_1.append(i)\n",
    "        if len(record_1)!=0:\n",
    "            return record_1[0]\n",
    "        else:\n",
    "            return \" \""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        dic={}\n",
    "        for i in arr:\n",
    "            if i in dic:\n",
    "                dic[i]+=1\n",
    "            else:\n",
    "                dic[i]=0\n",
    "        for j in dic:\n",
    "            if dic[j]==0:\n",
    "                return j\n",
    "        return \" \"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        ans = ' '\n",
    "        hash = dict()\n",
    "        for c in arr:\n",
    "            hash[c] = hash.get(c, 0) + 1\n",
    "        for key, value in hash.items():\n",
    "            if value == 1:\n",
    "                ans = key\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        hmap = {}\n",
    "        for c in arr:\n",
    "            hmap[c] = not c in hmap\n",
    "        for c in arr:\n",
    "            if hmap[c]:\n",
    "                return c \n",
    "        return ' '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        cnt = Counter(arr)\n",
    "        for ele in arr:\n",
    "            if cnt[ele] == 1:\n",
    "                return ele\n",
    "        return ' '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        hmap = {}\n",
    "        for c in arr:\n",
    "            hmap[c] = not c in hmap\n",
    "        for c in arr:\n",
    "            if hmap[c]: return c\n",
    "        return ' '\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        dic={}\n",
    "        for i in arr:\n",
    "            if i in dic:\n",
    "                dic[i]+=1\n",
    "            else:\n",
    "                dic[i]=0\n",
    "        for j in dic:\n",
    "            if dic[j]==0:\n",
    "                return j\n",
    "        return \" \"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        ans = \" \"\n",
    "        i = 0\n",
    "        while i < len(arr):\n",
    "            if i != 0 and arr[i]  in arr[0:i]:\n",
    "                i+=1\n",
    "                continue\n",
    "            j = len(arr) - 1\n",
    "            while j > i and arr[i] != arr[j]:\n",
    "                # print(i,j)\n",
    "                j -= 1\n",
    "            if j == i: return arr[i]\n",
    "            i += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        i = 0\n",
    "        hashmap = {}\n",
    "        sortlist = []\n",
    "        for char in arr:\n",
    "            if char in hashmap:\n",
    "                hashmap[char] += 1\n",
    "            else:\n",
    "                hashmap[char] = 1\n",
    "        for char in arr:\n",
    "            if hashmap[char] == 1:\n",
    "                return char\n",
    "        return ' '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        dic={}\n",
    "        for string in arr:\n",
    "            dic[string]=dic.get(string,0)+1\n",
    "\n",
    "        for string in dic:\n",
    "            if dic[string]==1:\n",
    "                return string\n",
    "        return ' '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        if len(arr) == 0: return ' '\n",
    "        hash_dict = {}\n",
    "        for s in arr:\n",
    "            hash_dict[s] = (s not in hash_dict.keys())\n",
    "        for k, v in hash_dict.items():\n",
    "            if v:\n",
    "                return k\n",
    "        return ' '\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        dic={}\n",
    "        for i in arr:\n",
    "            if i in dic:\n",
    "                dic[i]+=1\n",
    "            else:\n",
    "                dic[i]=0\n",
    "        for j in dic:\n",
    "            if dic[j]==0:\n",
    "                return j\n",
    "        return \" \"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        for i in range(len(arr)):\n",
    "            if arr.count(arr[i]) == 1:\n",
    "                return arr[i]\n",
    "        return ' '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        dic = {}\n",
    "        for c in arr:\n",
    "            dic[c] = not c in dic\n",
    "        for c in arr:\n",
    "            if dic[c]:\n",
    "                return c\n",
    "        return \" \""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        map = {}\n",
    "        for ch in arr:\n",
    "            if ch not in map:\n",
    "                map[ch] = 1\n",
    "            else:\n",
    "                map[ch] += 1\n",
    "        for k, v in map.items():\n",
    "            if v == 1:\n",
    "                return k\n",
    "        return ' '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        dic={}\n",
    "        for i in arr:\n",
    "            # if i not in dic:\n",
    "            #     dic[i]=0\n",
    "            # else:\n",
    "            #     dic[i]+=1\n",
    "            dic[i]=not i in dic\n",
    "        for u in arr:\n",
    "            if dic[u]:\n",
    "                return u\n",
    "            # else:\n",
    "            #     return ' '\n",
    "        return ' '\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def dismantlingAction(self, arr: str) -> str:\n",
    "#         hmap = {}\n",
    "#         for c in arr:\n",
    "#             hmap[c] = not c in hmap\n",
    "#         for c in arr:\n",
    "#             if hmap[c]: return c\n",
    "#         return ' '\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        if not arr: return ' '\n",
    "\n",
    "        memory = {}\n",
    "        answer = {}\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] in memory:\n",
    "                if arr[i] in answer:\n",
    "                    del answer[arr[i]]\n",
    "            else:\n",
    "                memory[arr[i]] = None\n",
    "                answer[arr[i]] = None\n",
    "\n",
    "        if len(answer) == 0:\n",
    "            return ' '\n",
    "        else:\n",
    "            return list(answer)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        cnt = [0 for _ in range(256)]\n",
    "        for c in arr:\n",
    "            cnt[ord(c)] += 1\n",
    "        for c in arr:\n",
    "            if cnt[ord(c)] == 1:\n",
    "                return c\n",
    "        return ' '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        hmap={}\n",
    "        for c in arr:\n",
    "            hmap[c]=c not in hmap\n",
    "        for k,v in hmap.items():\n",
    "            if(v):\n",
    "                return k\n",
    "        return ' '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        hmap = collections.OrderedDict()\n",
    "        for c in arr:\n",
    "            hmap[c] = not c in hmap\n",
    "        for k, v in hmap.items():\n",
    "            if v: return k\n",
    "        return ' '\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        set_arr = collections.Counter(arr)\n",
    "        for i,v in set_arr.items():\n",
    "            if v == 1:\n",
    "                return i\n",
    "        \n",
    "        return ' '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        \"\"\"\n",
    "        i = 0\n",
    "        dic = {}\n",
    "        \n",
    "        for k in range(len(arr)):\n",
    "            if arr[k] in dic:\n",
    "                dic[arr[k]][1] += 1\n",
    "            else:\n",
    "                dic[arr[k]] = [i, 1]\n",
    "                i += 1\n",
    "        \n",
    "        # print(dic)\n",
    "        for key, v in dic.items():\n",
    "            if v[1] == 1:\n",
    "                return key\n",
    "      \n",
    "        return \" \"\n",
    "        \"\"\"\n",
    "\n",
    "        # 更简洁：\n",
    "        hmap = {}\n",
    "        for c in arr:\n",
    "            # 用1代表只出现1次，0代表出现过多次：\n",
    "            hmap[c] = c not in hmap\n",
    "        for c in arr:\n",
    "            if hmap[c]: return c\n",
    "        return \" \"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        hmap = {}\n",
    "        for c in arr:\n",
    "            hmap[c] = not c in hmap\n",
    "        for c in arr:\n",
    "            if hmap[c]: return c\n",
    "        return ' '\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        hmap={}\n",
    "        for i in arr:\n",
    "            hmap[i]= i not in hmap\n",
    "        for i in hmap:\n",
    "            if hmap[i]:\n",
    "                return i\n",
    "        return ' '\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        hashmap = {}\n",
    "        for a in arr:\n",
    "            hashmap[a] = not a in hashmap\n",
    "        for i,j in hashmap.items():\n",
    "            if j : return i\n",
    "        return ' '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        from collections import Counter\n",
    "        if not arr: return ' '\n",
    "        counter = dict(Counter(arr))\n",
    "        for i in counter:\n",
    "            if counter[i] == 1:\n",
    "                return i\n",
    "        return ' '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        dict = {}\n",
    "        for c in arr:\n",
    "            dict[c] = not c in dict\n",
    "        for c in arr:\n",
    "            if dict[c]:\n",
    "                return c\n",
    "        return ' '\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        hmap = {}\n",
    "        for c in arr:\n",
    "            hmap[c] = not c in hmap\n",
    "        for k, v in hmap.items():\n",
    "            if v: return k\n",
    "        return ' '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        for i in arr:\n",
    "            if arr.count(i) == 1:\n",
    "                return i\n",
    "        return \" \""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        ans = {}\n",
    "        for c in arr:\n",
    "            if c in ans:\n",
    "                ans[c] = False\n",
    "            else:\n",
    "                ans[c] = True\n",
    "        for c in arr:\n",
    "            if ans[c]:\n",
    "                return c\n",
    "        return ' '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        dic = {}\n",
    "        for i in arr:\n",
    "            if i not in dic: dic[i] = 1\n",
    "            else: dic[i] += 1\n",
    "        for k, v in dic.items():\n",
    "            if v == 1:\n",
    "                return k\n",
    "        return ' '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        # if len(arr) == 0:\n",
    "        #     return ' '\n",
    "        # d = {}\n",
    "        # for i in range(len(arr)):\n",
    "        #     if arr[i] in d:\n",
    "        #         d[arr[i]] = -1\n",
    "        #     else:\n",
    "        #         d[arr[i]] = i\n",
    "        # ans = None\n",
    "        # idx = len(arr)\n",
    "        # for k, v in d.items():\n",
    "        #     if v != -1 and v < idx:\n",
    "        #         ans, idx = k, v\n",
    "        # return ans if ans else ' '\n",
    "        \n",
    "        # # Collections解法\n",
    "        # try:\n",
    "        #     return arr[min([arr.index(c) for c, v in collections.Counter(arr).items() if v == 1])]\n",
    "        # except ValueError:\n",
    "        #     return ' '\n",
    "        \n",
    "        hmap = collections.OrderedDict()\n",
    "        for c in arr:\n",
    "            hmap[c] = not c in hmap\n",
    "        for k, v in hmap.items():\n",
    "            if v: return k\n",
    "        return ' '\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        hashmap = {}\n",
    "        for i in arr:\n",
    "            if i in hashmap:\n",
    "                hashmap[i] += 1\n",
    "            else:\n",
    "                hashmap[i] = 1\n",
    "        for i in hashmap.keys():\n",
    "            if hashmap[i] == 1:\n",
    "                return i \n",
    "        return ' '\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        from collections import Counter\n",
    "        if not arr: return ' '\n",
    "        counter = dict(Counter(arr))\n",
    "        for i in counter:\n",
    "            if counter[i] == 1:\n",
    "                return i\n",
    "        return ' '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        hmap = {}\n",
    "        for i in arr:\n",
    "            hmap[i] =  not i in hmap\n",
    "        for i in arr:\n",
    "            if hmap[i]:\n",
    "                return i\n",
    "        return ' '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        for i in arr:\n",
    "            if arr.count(i)==1:\n",
    "                return i\n",
    "            \n",
    "        return \" \"\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        dict1 = collections.defaultdict(int)\n",
    "        for s in arr:\n",
    "            dict1[s] += 1\n",
    "        for key, val in dict1.items():\n",
    "            if val == 1:\n",
    "                return key\n",
    "        return ' '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        dic = {}\n",
    "        for c in arr:\n",
    "            dic[c] = not c in dic\n",
    "        for c in arr:\n",
    "            if dic[c]:\n",
    "                return c\n",
    "        return \" \""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        count = [0 for _ in range(26)]\n",
    "        for c in arr:\n",
    "            count[ord(c) - ord('a')] += 1\n",
    "        for c in arr:\n",
    "            if count[ord(c) - ord('a')] == 1:\n",
    "                return c\n",
    "        return ' '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        # if len(arr) == 0:\n",
    "        #     return ' '\n",
    "        # d = {}\n",
    "        # for i in range(len(arr)):\n",
    "        #     if arr[i] in d:\n",
    "        #         d[arr[i]] = -1\n",
    "        #     else:\n",
    "        #         d[arr[i]] = i\n",
    "        # ans = None\n",
    "        # idx = len(arr)\n",
    "        # for k, v in d.items():\n",
    "        #     if v != -1 and v < idx:\n",
    "        #         ans, idx = k, v\n",
    "        # return ans if ans else ' '\n",
    "        \n",
    "        # # Collections解法\n",
    "        try:\n",
    "            return arr[min([arr.index(c) for c, v in collections.Counter(arr).items() if v == 1])]\n",
    "        except ValueError:\n",
    "            return ' '\n",
    "        \n",
    "        # hmap = collections.OrderedDict()\n",
    "        # for c in arr:\n",
    "        #     hmap[c] = not c in hmap\n",
    "        # for k, v in hmap.items():\n",
    "        #     if v: return k\n",
    "        # return ' '\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        hasmap = {}\n",
    "\n",
    "        for item in arr:\n",
    "            if item not in hasmap:\n",
    "                hasmap[item] = 1\n",
    "            else:\n",
    "                hasmap[item] = hasmap.get(item) + 1\n",
    "        \n",
    "        for key, value in hasmap.items():\n",
    "            if value == 1:\n",
    "                return key\n",
    "        return \" \""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        dic = {}\n",
    "        for c in arr:\n",
    "            dic[c] = not c in dic\n",
    "        for k,v in dic.items():\n",
    "            if v:\n",
    "                return k\n",
    "        return \" \""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        d = {}\n",
    "        for char in arr:\n",
    "            if char in d.keys():\n",
    "                d[char] += 1\n",
    "            else:\n",
    "                d[char] = 1\n",
    "        for k in d.keys():\n",
    "            if d[k] == 1:\n",
    "                return k\n",
    "        return \" \""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        hmap = {}\n",
    "        for c in arr:\n",
    "            hmap[c] = not c in hmap\n",
    "        for c in arr:\n",
    "            if hmap[c]: return c\n",
    "        return ' '\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        hash_t = dict()\n",
    "        res = ' '\n",
    "        l = len(arr)\n",
    "        for i in range(l):\n",
    "            if not arr[i] in hash_t:\n",
    "                hash_t.update({arr[i]:1})\n",
    "            else:\n",
    "                hash_t[arr[i]] += 1\n",
    "        for i,val in enumerate(hash_t):\n",
    "            if hash_t[val] == 1:\n",
    "                return val\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        hamp = {}\n",
    "        for i in arr:\n",
    "            if i not in hamp:\n",
    "                hamp[i] = True\n",
    "            else:\n",
    "                hamp[i] = False\n",
    "        for j in arr:\n",
    "            if hamp[j] == True:\n",
    "                return j\n",
    "        return ' '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        cnt = Counter(arr)\n",
    "        for k in cnt:\n",
    "            if cnt[k] == 1:\n",
    "                return k\n",
    "        return \" \""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        hmap={}\n",
    "        for c in arr:\n",
    "            hmap[c]=c not in hmap\n",
    "        for c in arr:\n",
    "            if(hmap[c]):\n",
    "                return c\n",
    "        return ' '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        list = []\n",
    "        for i in arr:\n",
    "            if i not in list:\n",
    "                list.append(i)\n",
    "        for i in list:\n",
    "            if arr.count(i)==1:\n",
    "                return i\n",
    "        return ' '\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        for i in arr:\n",
    "            if arr.count(i)==1:\n",
    "                return i \n",
    "        return ' '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        dic = {}\n",
    "        for i in arr:\n",
    "            if i not in dic: dic[i] = 1\n",
    "            else: dic[i] += 1\n",
    "        for i in arr:\n",
    "            if dic[i] == 1:\n",
    "                return i\n",
    "        return ' '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        dic = {}\n",
    "        for i in arr:\n",
    "            if i not in dic: dic[i] = 1\n",
    "            else: dic[i] += 1\n",
    "        for i in arr:\n",
    "            if dic[i] == 1:\n",
    "                return i\n",
    "        return ' '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        if len(arr) == 0:\n",
    "            return \" \"\n",
    "        elif len(arr) == 1:\n",
    "            return arr\n",
    "        else:\n",
    "            while len(arr) > 1:\n",
    "                for j in arr[1:]:\n",
    "                    if j == arr[0]:\n",
    "                        arr = arr.replace(j, '')\n",
    "                        break\n",
    "                else:\n",
    "                    return arr[0]\n",
    "            if len(arr) == 1:\n",
    "                return arr\n",
    "            else:\n",
    "                return \" \"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        # for i in arr:\n",
    "        #     if arr.count(i)==1:\n",
    "        #         return i\n",
    "            \n",
    "        # return \" \"\n",
    "        s = {}\n",
    "        for i in arr:\n",
    "            s[i] = not i in s\n",
    "        for k,v in s.items():\n",
    "            if v:\n",
    "                return k\n",
    "        return \" \""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        lst=[]\n",
    "        for i in arr:\n",
    "            if i not in lst:\n",
    "                cnt=arr.count(i)\n",
    "                if cnt==1:\n",
    "                    return i\n",
    "                    break\n",
    "        else:\n",
    "            return ' '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        hmap=[0]*26\n",
    "        a=ord('a')\n",
    "        for c in arr:\n",
    "            hmap[ord(c)-a]+=1\n",
    "        for c in arr:\n",
    "            if hmap[ord(c)-a]==1:\n",
    "                return c\n",
    "        return ' '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> str:\n",
    "        q1, q2 = [], []\n",
    "        for i in arr:\n",
    "            if i in q2 and i in q1:\n",
    "                q1.remove(i)\n",
    "            if i not in q2 and i not in q1:\n",
    "                q1.append(i)\n",
    "                q2.append(i)\n",
    "            \n",
    "        if q1:\n",
    "            return q1[0]\n",
    "        else:\n",
    "            return \" \"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        dic = {}\n",
    "        res = 0\n",
    "        l = -1\n",
    "\n",
    "        for i, ch in enumerate(arr):\n",
    "            if ch in dic:\n",
    "                l = max(l, dic[ch])\n",
    "            dic[ch] = i \n",
    "            res = max(res, i-l)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        i=0\n",
    "        j=0\n",
    "        a=set()\n",
    "        maxi=0\n",
    "        s=arr\n",
    "        while j<len(s):\n",
    "            if s[j] not in a:\n",
    "                a.add(s[j])\n",
    "                maxi=max(len(a),maxi)\n",
    "                j+=1\n",
    "            else:\n",
    "                a.remove(s[i])\n",
    "                i+=1\n",
    "        return maxi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        if arr == ' ': return 1\n",
    "\n",
    "        res = 0\n",
    "        left_dict = {}\n",
    "        l = -1\n",
    "        for r in range(len(arr)):\n",
    "            l = max(left_dict.get(arr[r], -1), l)\n",
    "            cur_len = r - l\n",
    "            res = max(res, cur_len)\n",
    "            left_dict[arr[r]] = r\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        h = {}\n",
    "        res = 0\n",
    "        temp = 0\n",
    "        for i in range(len(arr)):\n",
    "            j = h.get(arr[i], -1)\n",
    "            h[arr[i]] = i\n",
    "            if(temp < i - j): temp = temp + 1\n",
    "            else: temp = i - j\n",
    "            res = max(res, temp)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        n = len(arr)\n",
    "        if n < 2:\n",
    "            return n\n",
    "        look_up = set()\n",
    "        cur_len, max_len = 0, 0\n",
    "        left = 0\n",
    "        for char in arr:\n",
    "            cur_len += 1\n",
    "            while char in look_up:\n",
    "                look_up.remove(arr[left])\n",
    "                left += 1\n",
    "                cur_len -= 1\n",
    "            max_len = max(max_len, cur_len)\n",
    "            look_up.add(char)\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        m = {}\n",
    "        last = 0\n",
    "        maxVal = 0\n",
    "        for i, c in enumerate(arr):\n",
    "            # 如果不存在重复，则 f(i)=f(i-1)+1；\n",
    "            # 如果存在重复，求 min(f(i-1)+1, currIndex-lastIndex)\n",
    "            last=min(i - m.get(c, -1), last+1)\n",
    "            maxVal=max(maxVal, last)\n",
    "            m[c]=i\n",
    "        return maxVal\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        if not arr:\n",
    "            return 0\n",
    "        i = -1\n",
    "        res = 0\n",
    "        record = {}\n",
    "        for j in range(len(arr)):\n",
    "            if arr[j] in record:\n",
    "                i = max(record[arr[j]], i)\n",
    "            record[arr[j]] = j\n",
    "            res = max(res, j-i)\n",
    "\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        dic,res,i = {},0,-1\n",
    "        for j in range(len(arr)):\n",
    "            if arr[j] in dic:\n",
    "                i = max(dic[arr[j]],i)\n",
    "            dic[arr[j]] = j\n",
    "            res = max(res,j-i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        left, charSet = 0, set()\n",
    "        ans = 0\n",
    "        for right in range(len(arr)):\n",
    "            while arr[right] in charSet:\n",
    "                charSet.remove(arr[left])\n",
    "                left += 1\n",
    "            charSet.add(arr[right])\n",
    "            ans = max(ans, right-left+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        n = len(arr)\n",
    "        if n < 2:\n",
    "            return n\n",
    "        look_up = set()\n",
    "        cur_len, max_len = 0, 0\n",
    "        left = 0\n",
    "        for char in arr:\n",
    "            cur_len += 1\n",
    "            while char in look_up:\n",
    "                look_up.remove(arr[left])\n",
    "                left += 1\n",
    "                cur_len -= 1\n",
    "            max_len = max(max_len, cur_len)\n",
    "            look_up.add(char)\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        left = 0\n",
    "        right = 0\n",
    "        max_len = 0\n",
    "        length = len(arr)\n",
    "        if length <= 1:\n",
    "            return length\n",
    "        while right < length:\n",
    "            cur_char = arr[right]\n",
    "            right += 1\n",
    "\n",
    "            # 窗口串中 当前字符个数 > 1, 收缩\n",
    "            while arr[left:right].count(cur_char) > 1:\n",
    "                cur_len = right - 1 - left\n",
    "                # print(f\"cur_str: {arr[left:right - 1]}\")\n",
    "                if max_len < cur_len:\n",
    "                    max_len = cur_len\n",
    "                left += 1\n",
    "            else:\n",
    "                cur_len = right - left\n",
    "                if max_len < cur_len:\n",
    "                    max_len = cur_len\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        n =len(arr)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        \n",
    "        res = 0\n",
    "        record =defaultdict(int)\n",
    "        left, right = 0, 0\n",
    "        while right < n:\n",
    "            while right < n and record[arr[right]] == 0:\n",
    "                record[arr[right]] += 1\n",
    "                right += 1\n",
    "                \n",
    "            res = max(res, right-left)\n",
    "\n",
    "            while right < n and arr[left] != arr[right]:\n",
    "                record[arr[left]] -= 1\n",
    "                left += 1\n",
    "\n",
    "            record[arr[left]] -= 1\n",
    "            left += 1\n",
    "        \n",
    "        return res\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        dic, res, i = {}, 0, -1\n",
    "        for j in range(len(arr)):\n",
    "            if arr[j] in dic:\n",
    "                i = max(dic[arr[j]], i)\n",
    "            dic[arr[j]] = j\n",
    "            res = max(res, j - i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        data = []\n",
    "        maxlen = 0\n",
    "        for i in range(len(arr)):\n",
    "            x = arr[i]\n",
    "            if x not in data:\n",
    "                data.append(x)\n",
    "            else:\n",
    "                maxlen = max(maxlen, len(data))\n",
    "                data = data[data.index(x) + 1:]\n",
    "                data.append(x)\n",
    "        maxlen = max(maxlen, len(data))\n",
    "        return maxlen\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        if not arr:return 0\n",
    "        if len(arr) == 1:return 1\n",
    "        dic = {}\n",
    "        res = 0\n",
    "        i,j = 0,0\n",
    "        while i < len(arr):\n",
    "            if arr[i] in dic and dic[arr[i]] >= j:\n",
    "                j = dic[arr[i]] +1\n",
    "\n",
    "            dic[arr[i]] = i \n",
    "            res = max(res,i-j+1)\n",
    "                \n",
    "            i+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        ans = 0\n",
    "        windows = set()\n",
    "        left, right = 0, 0\n",
    "        while right < len(arr):\n",
    "            if arr[right] not in windows:\n",
    "                windows.add(arr[right])\n",
    "                right += 1\n",
    "            else:\n",
    "                while arr[left] != arr[right]:\n",
    "                    windows.remove(arr[left])\n",
    "                    left += 1\n",
    "\n",
    "                windows.remove(arr[left])\n",
    "                left += 1\n",
    "\n",
    "            ans = max(ans, len(windows))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(arr)):\n",
    "            kind = set()\n",
    "            j = i\n",
    "            while j < len(arr):\n",
    "                if arr[j] not in kind :\n",
    "                    kind.add(arr[j])\n",
    "                else :\n",
    "                    j = len(arr)\n",
    "                j += 1\n",
    "            ans = max(ans, len(kind))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        hmap = dict()\n",
    "        i, j, ans = 0, 0, 0\n",
    "        while j < len(arr):\n",
    "            while arr[j] in hmap:\n",
    "                hmap.pop(arr[i])\n",
    "                i += 1\n",
    "            ans = max(ans, j - i + 1)\n",
    "            hmap[arr[j]] = 1\n",
    "            j += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        max_result=0\n",
    "        c_result=0\n",
    "        c_str=\"\"\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] not in c_str:\n",
    "                c_result+=1\n",
    "                c_str+=arr[i]\n",
    "                max_result=max(max_result,c_result)\n",
    "            else:\n",
    "                last_index=c_str.find(arr[i])\n",
    "                c_str+=arr[i]\n",
    "                c_str=c_str[last_index+1:]\n",
    "                c_result=len(c_str)\n",
    "                max_result=max(max_result,c_result)\n",
    "        return max_result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        dic={}\n",
    "        ans=0\n",
    "        temp=0\n",
    "        for j in range(len(arr)):\n",
    "            i=dic.get(arr[j],-1)\n",
    "            dic[arr[j]]=j\n",
    "            if temp<j-i:\n",
    "                temp+=1\n",
    "            else:\n",
    "                temp=j-i\n",
    "            ans=max(ans,temp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        dic, res, i = {}, 0, -1\n",
    "        for j in range(len(arr)):\n",
    "            if arr[j] in dic:\n",
    "                i = max(dic[arr[j]], i)\n",
    "            dic[arr[j]] = j\n",
    "            res = max(res, j - i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        m=dict()\n",
    "        maxVal=0\n",
    "        left=-1\n",
    "        for i,char in enumerate(arr):\n",
    "            if char in m and m[char]>left:\n",
    "                left=m[char]\n",
    "            maxVal=max(maxVal, i-left)\n",
    "            m[char]=i\n",
    "        return maxVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        tailmap = {}\n",
    "        maxlen = 0\n",
    "        tailsidx = -1\n",
    "        for idx, item in enumerate(arr):\n",
    "            taillen,tailsidx = self.maxtail(tailmap, tailsidx, item, idx)\n",
    "            if taillen > maxlen:\n",
    "                maxlen = taillen\n",
    "        return maxlen\n",
    "\n",
    "    def maxtail(self, tailmap, tailsidx, tailitem, tailindex) -> (int,int):\n",
    "        preidx = tailmap.get(tailitem, -1)\n",
    "        if preidx > tailsidx:\n",
    "            tailsidx = preidx\n",
    "        taillen = tailindex - tailsidx\n",
    "        tailmap[tailitem] = tailindex\n",
    "        return taillen, tailsidx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        if len(arr)==0:\n",
    "            return 0\n",
    "        # 记录上一次这个字符出现的位置\n",
    "        pos=dict()\n",
    "        m=-1\n",
    "        result=0\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] not in pos:\n",
    "                result=max(result,i-m)\n",
    "            else:\n",
    "                m=max(pos[arr[i]],m)\n",
    "                result=max(result,i-m)\n",
    "            pos[arr[i]]=i\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- encoding: utf-8 -*-\n",
    "# @Author  :   Liang Hao \n",
    "# @Time    :   2023/11/10 15:48:53\n",
    "# @File    :   LCR_167.py\n",
    "# @Contact   :   lianghao@whu.edu.cn\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, s):\n",
    "        window = {}\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "        left, right = 0, 0\n",
    "        \n",
    "        while right < n:\n",
    "            c = s[right]\n",
    "            right  = right + 1\n",
    "            \n",
    "            window[c] = window.get(c, 0) + 1\n",
    "            \n",
    "            while window[c] > 1:\n",
    "                d = s[left]\n",
    "                left = left + 1\n",
    "                window[d] = window[d] - 1\n",
    "            \n",
    "            ans = max(ans, right - left)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        dic = {}\n",
    "        left, ans = -1, 0\n",
    "        for right in range(len(arr)):\n",
    "            if arr[right] in dic:\n",
    "                left = max(left, dic[arr[right]])\n",
    "            dic[arr[right]] = right\n",
    "            ans = max(ans, right - left)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        ans = 0\n",
    "        head = 0\n",
    "        kind = set()\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] not in kind :\n",
    "                kind.add(arr[i])\n",
    "            else :\n",
    "                ans = max(ans, len(kind))\n",
    "                while kind and arr[head] != arr[i]:\n",
    "                    kind.remove(arr[head])\n",
    "                    head += 1\n",
    "                head += 1\n",
    "        return max(ans, len(kind))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        dic = {}\n",
    "        res = tmp = 0\n",
    "        for j in range(len(arr)):\n",
    "            i = dic.get(arr[j], -1) # 获取索引 i\n",
    "            dic[arr[j]] = j # 更新哈希表\n",
    "            tmp = tmp + 1 if tmp < j - i else j - i # dp[j - 1] -> dp[j]\n",
    "            res = max(res, tmp) # max(dp[j - 1], dp[j])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        # 思路是滑动串口\n",
    "        left = 0 \n",
    "        hashmap = {}\n",
    "        res = 0\n",
    "        for right in range(len(arr)):\n",
    "            if arr[right] in hashmap:\n",
    "                hashmap[arr[right]] += 1\n",
    "            else:\n",
    "                hashmap[arr[right]] = 1\n",
    "\n",
    "            while hashmap[arr[right]] > 1:\n",
    "                hashmap[arr[left]] -= 1\n",
    "                if hashmap[arr[left]] == 0:\n",
    "                    del hashmap[arr[left]]\n",
    "                left += 1\n",
    "\n",
    "            res = max(right-left+1,res) \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        if not arr:return 0\n",
    "        if len(arr) == 1:return 1\n",
    "        dic = {}\n",
    "        res = 0\n",
    "        i,j = 0,0\n",
    "        while i < len(arr):\n",
    "            if arr[i] in dic and dic[arr[i]] >= j:\n",
    "                j = dic[arr[i]] +1\n",
    "\n",
    "            dic[arr[i]] = i \n",
    "            res = max(res,i-j+1)\n",
    "                \n",
    "            i+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        res, i, dic = 0,  -1, {}\n",
    "        for ind, s in enumerate(arr):\n",
    "            if s in dic:\n",
    "                i = max(i, dic[s])\n",
    "            dic[s] = ind\n",
    "            res = max(res, ind - i)\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        res ,i = 0 , -1\n",
    "        dic = {}\n",
    "        for ind, s in enumerate(arr):\n",
    "            if s in dic:\n",
    "                i = max(i, dic[s])\n",
    "            dic[s] = ind \n",
    "            res = max(res, ind - i)\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        dic = {}\n",
    "        ans = 0\n",
    "        left = -1\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] in dic:\n",
    "                left = max(dic[arr[i]], left)\n",
    "            dic[arr[i]] = i\n",
    "            ans = max(ans, i-left)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        dic, res, i = {}, 0, -1\n",
    "        for j in range(len(arr)):\n",
    "            if arr[j] in dic:\n",
    "                i = max(i, dic[arr[j]])\n",
    "            dic[arr[j]] = j\n",
    "            res = max(res, j-i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, s: str) -> int:\n",
    "        length = len(s)\n",
    "        max_length = 0\n",
    "        start = 0\n",
    "        end = 1\n",
    "        dp = [1] * length\n",
    "        if len(s) == 1:\n",
    "            return 1\n",
    "        for i in range(1, length):\n",
    "            end = i+1\n",
    "            clip = s[start:i]\n",
    "            \n",
    "            if s[i] in clip:\n",
    "                while(s[start] != s[i]):\n",
    "                    start += 1\n",
    "                start += 1\n",
    "                if end - start == 1:\n",
    "                    dp[i] = 1\n",
    "                else:\n",
    "                    dp[i] = end - start\n",
    "\n",
    "            else:\n",
    "                dp[i] = dp[i-1] + 1\n",
    "            \n",
    "            max_length = max(max_length, dp[i])\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        windows = collections.defaultdict(int)\n",
    "        res = 0\n",
    "        left, right = 0, 0\n",
    "        while right < len(arr):\n",
    "            c = arr[right]\n",
    "            right += 1\n",
    "            windows[c] += 1            \n",
    "            while windows[c] > 1:\n",
    "                d = arr[left]\n",
    "                left += 1\n",
    "                windows[d] -= 1\n",
    "            res = max(res, right - left)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        dic,res,i = {},0,-1\n",
    "        for j in range(len(arr)):\n",
    "            if arr[j] in dic:\n",
    "                i = max(dic[arr[j]],i)\n",
    "            dic[arr[j]] = j\n",
    "            res = max(j - i,res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        dic = {}\n",
    "        res = tmp = 0\n",
    "        for j in range(len(arr)):\n",
    "            i = dic.get(arr[j], -1) # 获取索引 i\n",
    "            dic[arr[j]] = j # 更新哈希表\n",
    "            tmp = tmp + 1 if tmp < j - i else j - i # dp[j - 1] -> dp[j]\n",
    "            res = max(res, tmp) # max(dp[j - 1], dp[j])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        mp = {}\n",
    "        j=-1\n",
    "        res = 0\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] in mp: \n",
    "                j = max(mp[arr[i]],j)\n",
    "            \n",
    "            res = max(i-j,res)\n",
    "            mp[arr[i]] = i\n",
    "            \n",
    "            \n",
    "\n",
    "        return res\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        n = len(arr)\n",
    "        hashmap = {}\n",
    "        head, res = 0, 0\n",
    "        for tail in range(n):\n",
    "            if arr[tail] in hashmap:\n",
    "                head = max(hashmap[arr[tail]], head)\n",
    "            hashmap[arr[tail]] = tail + 1\n",
    "            res = max(res, tail - head + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        # arr = arr.lower()\n",
    "        # print(arr)\n",
    "        left = right = 0\n",
    "        path = set()\n",
    "        max_len = 0\n",
    "        while right<len(arr):\n",
    "            while left<right and arr[right] in path:\n",
    "                path.remove(arr[left])\n",
    "                left+=1\n",
    "            path.add(arr[right])\n",
    "            \n",
    "            max_len = max(max_len, right-left+1)\n",
    "            right+=1\n",
    "            \n",
    "        return max_len\n",
    "        \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        dic, res, i = {}, 0 , -1\n",
    "        for j in range(len(arr)):\n",
    "            if arr[j] in dic:\n",
    "                i = max(dic.get(arr[j]), i)\n",
    "            dic[arr[j]]= j\n",
    "            res = max(res, j-i)\n",
    "                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://labuladong.gitee.io/algo/di-ling-zh-bfe1b/wo-xie-le--f02cd/\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        s = arr\n",
    "\n",
    "        windows = defaultdict(int)\n",
    "        left = right = 0\n",
    "        res = 0\n",
    "\n",
    "        while right < len(s):\n",
    "            c = s[right]\n",
    "            right += 1\n",
    "            windows[c] += 1\n",
    "\n",
    "            while windows[c] > 1:\n",
    "                d = s[left]\n",
    "                left += 1\n",
    "                windows[d] -= 1\n",
    "            \n",
    "            res = max(res, right - left)\n",
    "    \n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        dic, res, i = {}, 0 , -1\n",
    "        for j in range(len(arr)):\n",
    "            if arr[j] in dic:\n",
    "                i = max(dic.get(arr[j]), i)\n",
    "            dic[arr[j]]= j\n",
    "            res = max(res, j-i)\n",
    "                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, s: str) -> int:\n",
    "        length = len(s)\n",
    "        max_length = 0\n",
    "        start = 0\n",
    "        end = 1\n",
    "        dp = [1] * length\n",
    "        if len(s) == 1:\n",
    "            return 1\n",
    "        for i in range(1, length):\n",
    "            end = i+1\n",
    "            clip = set(s[start:i])\n",
    "            \n",
    "            if s[i] in clip:\n",
    "                while(s[start] != s[i]):\n",
    "                    start += 1\n",
    "                start += 1\n",
    "                if end - start == 1:\n",
    "                    dp[i] = 1\n",
    "                else:\n",
    "                    dp[i] = end - start\n",
    "\n",
    "            else:\n",
    "                dp[i] = dp[i-1] + 1\n",
    "            \n",
    "            max_length = max(max_length, dp[i])\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, list: str) -> int:\n",
    "        dp = [0] * len(list)\n",
    "        n = len(list)\n",
    "        if n ==0:\n",
    "            return 0\n",
    "        else:\n",
    "            dp[0] = 1\n",
    "            for i in range(n):\n",
    "                temp = -1\n",
    "                for j in reversed(range(i)):\n",
    "                    if list[j] == list[i]:\n",
    "                        temp = j\n",
    "                        break\n",
    "                if dp[i-1] < i - temp:\n",
    "                    dp[i] = dp[i-1] + 1\n",
    "                else:\n",
    "                    dp[i] = i - temp\n",
    "            return max(dp)\n",
    "                \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, s: str) -> int:\n",
    "        length = len(s)\n",
    "        max_length = 0\n",
    "        start = 0\n",
    "        end = 1\n",
    "        dp = [1] * length\n",
    "        if len(s) == 1:\n",
    "            return 1\n",
    "        for i in range(1, length):\n",
    "            end = i+1\n",
    "            clip = set(s[start:i])\n",
    "            \n",
    "            if s[i] in clip:\n",
    "                while(s[start] != s[i]):\n",
    "                    start += 1\n",
    "                start += 1\n",
    "                if end - start == 1:\n",
    "                    dp[i] = 1\n",
    "                else:\n",
    "                    dp[i] = end - start\n",
    "\n",
    "            else:\n",
    "                dp[i] = dp[i-1] + 1\n",
    "            \n",
    "            max_length = max(max_length, dp[i])\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        if len(arr)==0:\n",
    "            return 0\n",
    "        \n",
    "        ret = 1\n",
    "        d = {arr[-1]:len(arr)-1}\n",
    "        mp = [1]*len(arr)\n",
    "        for i in range(len(arr)-2,-1,-1):\n",
    "            c = arr[i]\n",
    "            np = d.get(c,float('inf'))\n",
    "            mp[i] = min(1+mp[i+1],np-i)\n",
    "            ret = max(mp[i],ret)\n",
    "            d[c] = i\n",
    "        \n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, s: str) -> int:\n",
    "        loc = defaultdict()\n",
    "        max_combo = [0]*(len(s)+1)\n",
    "        for i in range(len(s)):\n",
    "            j = loc.get(s[i],-1)\n",
    "            loc[s[i]] = i\n",
    "            if i-max_combo[i]>j:\n",
    "                max_combo[i+1] = max_combo[i]+1\n",
    "            else:\n",
    "                max_combo[i+1] = i-j\n",
    "\n",
    "        return max(max_combo)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        #遍历 []存储长度 一旦找到重复的，那么窗口滑动到重复值的下一个\n",
    "        if len(arr) == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            dp = [0]*(len(arr))\n",
    "            dp[0] = 1\n",
    "            m=0\n",
    "        # pos = arr[1:2].find(arr[2])\n",
    "        # print(pos)\n",
    "            for i in range(1,len(arr)):\n",
    "                pos = arr[m:i].find(arr[i])\n",
    "                pos += m\n",
    "                if pos != -1:\n",
    "                # print(pos)\n",
    "                    m = pos + 1\n",
    "                    dp[i] = i - pos\n",
    "                else:\n",
    "             \n",
    "                    dp[i] = dp[i-1] + 1\n",
    "            return max(dp)\n",
    "            \n",
    "            \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        # 最长无重复子串\n",
    "        # dp[i]表示以i为结尾的最长长度\n",
    "        if not arr:\n",
    "            return 0\n",
    "        dic = {arr[0]:0}\n",
    "        n = len(arr)\n",
    "        dp = [1]*n\n",
    "        for i in range(1,n):\n",
    "            if arr[i] not in dic:\n",
    "                dp[i] = dp[i-1]+1\n",
    "            else:\n",
    "                if dic[arr[i]] < i-dp[i-1]:\n",
    "                    dp[i] = dp[i-1]+1\n",
    "                else:\n",
    "                    dp[i] = i-dic[arr[i]]\n",
    "            dic[arr[i]] = i\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, s: str) -> int:\n",
    "        length = len(s)\n",
    "        max_length = 0\n",
    "        start = 0\n",
    "        end = 1\n",
    "        dp = [1] * length\n",
    "        if len(s) == 1:\n",
    "            return 1\n",
    "        for i in range(1, length):\n",
    "            end = i+1\n",
    "            clip = s[start:i]\n",
    "            \n",
    "            if s[i] in clip:\n",
    "                while(s[start] != s[i]):\n",
    "                    start += 1\n",
    "                start += 1\n",
    "                # if end - start == 1:\n",
    "                #     dp[i] = 1\n",
    "                # else:\n",
    "                dp[i] = end - start\n",
    "\n",
    "            else:\n",
    "                dp[i] = dp[i-1] + 1\n",
    "            \n",
    "            max_length = max(max_length, dp[i])\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        if len(arr)==0: return 0\n",
    "        dic={}\n",
    "        n=len(arr)\n",
    "        dp=[0]*n\n",
    "        dic[arr[0]]=0\n",
    "        l=-1\n",
    "        r=0\n",
    "        dp[0]=1\n",
    "        for i in range(1,n):\n",
    "            if arr[i] in dic:\n",
    "                l=max(l,dic.get(arr[i]))\n",
    "            dic[arr[i]]=i\n",
    "            dp[i]=dp[i-1]+1 if dp[i-1]<i-l else dp[i-1]\n",
    "        return dp[n-1]\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, s: str) -> int:\n",
    "        length = len(s)\n",
    "        max_length = 0\n",
    "        start = 0\n",
    "        end = 1\n",
    "        dp = [1] * length\n",
    "        if len(s) == 1:\n",
    "            return 1\n",
    "        for i in range(1, length):\n",
    "            end = i+1\n",
    "            clip = s[start:i]\n",
    "            \n",
    "            if s[i] in clip:\n",
    "                while(s[start] != s[i]):\n",
    "                    start += 1\n",
    "                start += 1\n",
    "                if end - start == 1:\n",
    "                    dp[i] = 1\n",
    "                else:\n",
    "                    dp[i] = end - start\n",
    "\n",
    "            else:\n",
    "                dp[i] = dp[i-1] + 1\n",
    "            \n",
    "            max_length = max(max_length, dp[i])\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, s: str) -> int:\n",
    "        length = len(s)\n",
    "        max_length = 0\n",
    "        start = 0\n",
    "        end = 1\n",
    "        dp = [1] * length\n",
    "        if len(s) == 1:\n",
    "            return 1\n",
    "        for i in range(1, length):\n",
    "            end = i+1\n",
    "            clip = set(s[start:i])\n",
    "            \n",
    "            if s[i] in clip:\n",
    "                while(s[start] != s[i]):\n",
    "                    start += 1\n",
    "                start += 1\n",
    "                if end - start == 1:\n",
    "                    dp[i] = 1\n",
    "                else:\n",
    "                    dp[i] = end - start\n",
    "\n",
    "            else:\n",
    "                dp[i] = dp[i-1] + 1\n",
    "            \n",
    "            max_length = max(max_length, dp[i])\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        if not arr: return 0\n",
    "        n = len(arr)\n",
    "        if n == 1: return 1 \n",
    "        dp = [1]*(n+1)\n",
    "        dp[0] = 0\n",
    "        dic = {}\n",
    "        dic[arr[0]] = 0\n",
    "        for i in range(2, n+1):\n",
    "            cur = arr[i-1]\n",
    "            if cur not in dic:\n",
    "                dp[i] = dp[i-1] + 1\n",
    "            else:\n",
    "                leng = i-1-dic[arr[i-1]]\n",
    "                if leng > dp[i-1]:\n",
    "                    dp[i] = dp[i-1] + 1\n",
    "                else:\n",
    "                    dp[i] = leng \n",
    "            dic[arr[i-1]] = i-1 \n",
    "        return max(dp)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        n = len(arr)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        dp = [0]*(n)\n",
    "        dp[0] = 1\n",
    "        record = {arr[0]:0}\n",
    "        for i in range(1, n):\n",
    "            if arr[i] in record:\n",
    "                j = record[arr[i]]\n",
    "                if dp[i-1] >= i-j:\n",
    "                    dp[i] = i-j\n",
    "                else:\n",
    "                    dp[i] = dp[i-1]+1\n",
    "            else:\n",
    "                dp[i] = dp[i-1]+1\n",
    "            record[arr[i]] = i\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        if len(arr) == 0:\n",
    "            return 0\n",
    "        last_len = [1]\n",
    "        for i in range(1,len(arr)):\n",
    "            k = 1\n",
    "            while k <= last_len[-1]:\n",
    "                if arr[i] == arr[i - k]:\n",
    "\n",
    "                    break \n",
    "                k += 1\n",
    "            last_len.append(k) \n",
    "        return max(last_len)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dismantlingAction(self, arr: str) -> int:\n",
    "        a = []\n",
    "        arr = list(arr)\n",
    "        n = len(arr)\n",
    "        i = 0\n",
    "        if n <= 1:\n",
    "            return n\n",
    "\n",
    "\n",
    "        def dfs(s):\n",
    "            _map = set()\n",
    "            for x in s:\n",
    "                if x in _map:\n",
    "                    return len(_map)\n",
    "                else:\n",
    "                    _map.update(x)\n",
    "            return len(_map)\n",
    "\n",
    "        while i < n:\n",
    "            a.append(dfs(arr))\n",
    "            arr.pop(0)\n",
    "            i += 1\n",
    "        return max(a)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
